package kyssion.leetcode.num101_150;

import kyssion.leetcode.util.ListNode;

import java.util.ArrayList;
import java.util.List;

public class code143_链表重排序 {

    public static void main(String[] args) {
        ListNode listNode = ListNode.createListNode(
                new int[]{
                        1, 2, 3, 4, 5, 6, 7
                }
        );
        new code143_链表重排序().reorderList2(listNode);
        System.out.println();
    }

    public void reorderList(ListNode head) {
        if (head == null) {
            return;
        }
        List<ListNode> listNodes = new ArrayList<>();
        while (head != null) {
            listNodes.add(head);
            head = head.next;
        }
        int end = listNodes.size() - 1;
        int start = 0;
        while (true) {
            if (start + 1 < end) {
                listNodes.get(start).next = listNodes.get(end);
                listNodes.get(end).next = listNodes.get(start + 1);
            } else {
                break;
            }
            start++;
            end--;
        }
        listNodes.get(end).next = null;
    }

    /**
     * 使用二进法 在一个循环中得到中位
     * 之后回转中位到末尾
     * 然后一二插入
     * @param head
     */
    public void reorderList2(ListNode head) {
        if (head == null || head.next == null)
            return;
        ListNode head0 = head;
        ListNode fast = head;
        ListNode slow = head;
        ListNode pre = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            pre = slow;
            slow = slow.next;
        }
        pre.next = null;
        ListNode h0 = null;
        ListNode h1 = slow;
        ListNode h2 = slow.next;
        while (h1 != null) {
            h2 = h1.next;
            h1.next = h0;
            h0 = h1;
            h1 = h2;
        }
        ListNode head1 = h0;
        while (head0 != null) {
            h0 = head0.next;
            h1 = head1.next;
            head0.next = head1;
            if (h0 != null)
                head1.next = h0;
            head0 = h0;
            head1 = h1;
        }
    }

}
